Certain filesystem metadata data structures are critical to the correct functionality of the filesystem. It is desirable to be able to detect corruption of these structures easily and reliably.
Some level of validation can be provided by embedding validation information such as a CRC in each block of filesystem metadata. However, this only provides validation of the block in isolation. It is possible that a valid block A and a valid block B may combine to form an invalid structure AB.
A more rigorous validator would be one which validated the structure as a whole. One method for achieving this would be to calculate a CRC across the entire structure. However, such a solution has the disadvantage that the entire structure would have to be read (to calculate the new CRC value) whenever any part of the structure changed. Another option would be to keep a checksum of the entire structure. This would allow the new checksum to be calculated without having to read the entire structure, since the checksum of the old data could be removed from the overall checksum and then the checksum of the new data inserted. However, a checksum provides only a weak level of protection for large structures since, for example, two errors may cancel each other out, leaving a correct checksum despite the incorrect contents.
Some prior art systems maintain a list of the CRCs for the files in a storage system (e.g., http://www.dogma.net/markn/articles/crcman/crcman.htm) or for the blocks in a file (e.g., http://filerepair.sourceforge.net/), the contents of which are hereby incorporated herein by reference in their entireties.